package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-04-12 23:03
 */
public class QLint98 {
//    public ListNode sortList(ListNode head) {
//        if(head == null || head.next == null) {
//            return head;
//        }
//
//        ListNode mid = getMid(head);
//        ListNode head2 = mid.next;
//        mid.next = null;
//
//        ListNode left = sortList(head);
//        ListNode right = sortList(head2);
//
//        return mergeTwoLists(left, right);
//    }
//
//    private ListNode getMid(ListNode head) {
//        ListNode slow = head, fast = head;
//        while(fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//
//        return slow;
//    }
//
//    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//        ListNode dummy = new ListNode(0);
//        ListNode node = dummy;
//
//        while(l1 != null && l2 != null) {
//            if(l1.val <= l2.val) {
//                node.next = l1;
//                l1 = l1.next;
//            } else {
//                node.next = l2;
//                l2 = l2.next;
//            }
//            node = node.next;
//        }
//
//        if(l1 != null) {
//            node.next = l1;
//        }
//
//        if(l2 != null) {
//            node.next = l2;
//        }
//
//        return dummy.next;
//    }
}
